package com.cn.codebrush.动态规划;

/**
 * @Author Boolean
 * @Date 2022/5/13 15:29
 * @Version 1.0
 */
public class No64最小路径和 {
    public static void main(String[] args) {
        int[][] grid = {{1,3,1}, {1,5,1},{4,2,1}};
        System.out.println(minPathSum(grid));
    }

    public static int minPathSum(int[][] grid) {
        int m = grid[0].length;
        int n = grid.length;

        int[][] dp = new int[m][n];
        // dp[i][j] = min(dp[i-1][j] + dp[i][j],dp[i][j-1] + dp[i][j]);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0){
                    dp[i][j] = grid[i][j];
                }else if(j==0){
                    dp[i][j] = dp[i-1][0] + grid[j][i];
                }else if(i==0){
                    dp[i][j] = dp[0][j-1] + grid[j][i];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j] + grid[j][i],dp[i][j-1] + grid[j][i]);
                }
            }

        }

         return dp[m-1][n-1];
    }
}
